import java.util.Arrays;

public class 两地调度 {

    public int twoCitySchedCost(int[][] costs) {
        int n = costs.length;
        int sum = 0; // 算前往 a 地所需要的费用
        int[] arr = new int[n]; // 从 a 转化成去 b 需要花多少钱
        for (int i = 0; i < n; i++) {
            sum += costs[i][0]; // 所有去 a 相加
            arr[i] = costs[i][1] - costs[i][0]; // 算去 a 需要补多少差价
        }
        Arrays.sort(arr); // 按转化从小到大排序
        n /= 2; // 一半转化
        for (int i = 0; i < n; i++) {
            sum += arr[i]; // 补差价
        }
        return sum;
    }
}
